package sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

/**
 * 划分多个范围相同的区间，每个子区间自排序，最后合并
 * 参考：https://blog.csdn.net/qq_27124771/article/details/87651495
 * 弊端：
 * .如果桶数量计算方法是：int bucketNum = (max - min) / arr.length + 1;
 * 那么示例中，桶的数量应该是(50 - 11) / 6 + 1 = 7，而非图中画的4个桶.
 * 2.假设极端情况，max - min = 100, length = 10000, 那么按公式计算桶数量bucketNum =100/10000 + 1 = 1，也就是说只有一个桶了。这明显不符合常理，而且算法自动失效（因为只有一个桶了）
 * 8w 数据 0。081s
 * AND 桶排序的稳定性取决于桶内排序使用的算法。
 */
public class BucketSorting {
    public static void main(String[] args) {
        int[] arr = {49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
        costTime();
    }

    public static void bucketSort(int[] arr){

        // 计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        // 计算桶的数量, 在这如果用二维数组反而不太方便
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            // 创建桶。
            bucketArr.add(new ArrayList<>());
        }

        // 将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }

        // 对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            // Collections的sort方法使用的是归并排序
            Collections.sort(bucketArr.get(i));
        }

        // 将桶中的元素赋值到原序列
        int index = 0;
        for(int i = 0; i < bucketArr.size(); i++){
            for(int j = 0; j < bucketArr.get(i).size(); j++){
                arr[index++] = bucketArr.get(i).get(j);
            }
        }
    }
    /**
     *  测试八万的数据
     */
    public static void costTime() {
        int[] arrays3 = new int[80000];
        Random random2 = new Random();
        for (int i = 0; i < arrays3.length; i++) {
            arrays3[i] = random2.nextInt(80000);
        }
        long startTime = System.currentTimeMillis();
        bucketSort(arrays3);   // 正规的插入，有值的后移
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间优化时间为：" + (endTime - startTime)*0.001 + "s"); //输出程序运行时间
    }

}
